// Stack 栈
// 插入和删除的一端为栈顶，另一端为栈底
// 特点是LIFO原则，即后进后出
// 用数组实现一般认为更好

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int STDataType;
typedef struct Stack
{
    STDataType *data;
    int top;
    int capacity;
}Stack;

void StackInit(Stack* ps);
void StackDestroy(Stack* ps);

void StackPush(Stack* ps, STDataType val);
void StackPop(Stack* ps);

STDataType StackTop(Stack* ps);
int StackSize(Stack* ps);
bool isStackEmpty(Stack* ps);

void StackInit(Stack* ps)
{
    assert(ps);

    ps->data = (STDataType*)malloc(sizeof(STDataType) * 4);
    if (ps->data == NULL){
        printf("malloc fail\n");
        exit(-1);
    }

    ps->capacity = 4;
    ps->top = 0;
}

void StackDestroy(Stack* ps)
{
    assert(ps);

    free(ps->data);
    ps->data = NULL;
    ps->top = ps->capacity = 0;
}

void StackPush(Stack* ps, STDataType val)
{
    assert(ps);

    if (ps->top == ps->capacity){
        STDataType* tmp = (STDataType*)realloc(ps->data, ps->capacity * 2 * sizeof(STDataType));
        if (tmp == NULL){
            printf("realloc fail\n");
            exit(-1);
        }
        else {
            ps->data = tmp;
            ps->capacity *= 2;
        }
    }

    ps->data[ps->top] = val;
    ps->top++;
}

void StackPop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0); // 栈空时报错

    ps->top--;
}

STDataType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0); // 栈空时报错

    return ps->data[ps->top - 1];
}

int StackSize(Stack* ps)
{
    assert(ps);

    return ps->top;
}

bool isStackEmpty(Stack* ps)
{
    assert(ps);

    return ps->top == 0;
}

int main(void)
{
    // 初始化
    Stack st;
    StackInit(&st);

    // 压栈
    StackPush(&st, 1);
    StackPush(&st, 2);
    StackPush(&st, 3);

    // 取数据
    while(!isStackEmpty(&st)){
        printf("%d ", StackTop(&st));
        StackPop(&st);
    }
    putchar('\n');

    // 销毁栈
    StackDestroy(&st);

    return 0;
}






































